var arr = [3,2,5,8,4,7,6,9]
//1.冒泡排序
//冒泡排序的思想就是不断进行相邻交换，较小的数字如同气泡般慢慢浮到上面。
//优化：如果在排第i个元素时，没有交换任何元素，则排序已完成，无需继续遍历
//最好情况：O(n)
//最坏情况：O(n^2)
//平均情况：O(n^2)
function mSort(array){
    var flag=true;   //是否还要继续排序，排序优化
    for(var i=0;i<array.length-1 && flag;i++){
        flag=false;
        for(var j=array.length-2;j>=i;j--){
            if(array[j]>array[j+1]){
                var temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                flag=true;
            }
        }
    }
    return array;
}

//2.选择排序
//选择排序的思想是每次遍历找到最小的元素，然后和相应位置的元素交换位置。
//最好情况：O(n^2)
//最坏情况：O(n^2)
//平均情况：O(n^2)
function sSort(array){
    for(var i=0;i<array.length-1;i++){
        for(var j=i+1;j<array.length;j++){
            if(array[j]<array[i]){
                var temp=array[i];
                array[i]=array[j];
                array[j]=temp;
            }
        }
    }
    return array;
}

//3.插入排序
//插入排序的主要思想是将一个记录插入到已经安排好的有序表中，需要一个辅助空间来存放这个记录，以方便前面的元素进行右移。
//最好情况：O(n)
//最坏情况：O(n^2)
//平均情况：O(n^2)
function iSort(array){
    for(var i=1;i<array.length;i++){
        var temp=array[i];
        //将前面大于其的元素右移
        for(var j=i-1;array[j]>temp && j>=0;j--){
            array[j+1]=array[j];
        }
        //将记录插入对应位置
        array[j+1]=temp;
    }
    return array
}

//4.快速排序
//选择一个基准元素(通常选择第一个元素)，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有元素都比基准元素小，另外一部分的所有元素大于或等于基准元素大。同样方法依次分割；整个排序过程可以递归进行。
//最好情况：O(nlog n)
//最坏情况：O(n^2)
//平均情况：O(nlog n)
function quickSort(arr) {
    if (arr.length <= 1) return ;
    
    //取数组最接近中间的数位基准，奇数与偶数取值不同，但不印象，当然，你可以选取第一个，或者最后一个数为基准，这里不作过多描述
    var pivotIndex = Math.floor(arr.length / 2);
    var pivot = arr.splice(pivotIndex, 1)[0];
    //左右区间，用于存放排序后的数
    var left = [];
    var right = [];

    console.log('基准为：' + pivot + ' 时');
    for (var i = 0; i < arr.length; i++) {
        console.log('分区操作的第 ' + (i + 1) + ' 次循环：');
        //小于基准，放于左区间，大于基准，放于右区间
        if (arr[i] < pivot) {
            left.push(arr[i]);
            console.log('左边：' + (arr[i]))
        } else {
            right.push(arr[i]);
            console.log('右边：' + (arr[i]))
        }
    }
    //这里使用concat操作符，将左区间，基准，右区间拼接为一个新数组
    //然后递归1，2步骤，直至所有无序区间都 只剩下一个元素 ，递归结束
    return quickSort(left).concat([pivot], quickSort(right));
}
console.log(quickSort(arr));
